package org.example.algorithm.LinkList;

import java.util.*;

public class Test {

    /**
     * 141.环形列表
     * 给你一个链表的头节点 head ，判断链表中是否有环。
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，
     * 评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
     * 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
     */
    public boolean hasCycle(ListNode head) {
        ListNode cycle = head;
        Set<Integer> set = new HashSet<>();
        while (cycle.next != null) {
            if (set.contains(cycle.val)) {
                return false;
            }
            set.add(cycle.val);
            cycle = cycle.next;
        }
        return true;
    }

    public static void main(String[] args) {
//        ListNode listNode = makeListNode("1,4,2,5,2,6,5,7,9");
        ListNode listNode = makeListNode("1,2,3,3,4,4,5");
        printListNode(listNode);
        printListNode(deleteDuplicates(listNode));
//        List<ListNode> listNodes = splitListNodeByNumber(listNode, 5);
//        for (ListNode item : listNodes) {
//            printListNode(item);
//        }
    }

    private static void printListNode(ListNode item) {
        ListNode index = item;
        StringBuilder sb = new StringBuilder();
        while (index != null) {
            sb.append(index.val).append(" ");
            index = index.next;
        }
        System.out.println(sb.toString());
    }

    /**
     * 武汉腾讯面试Hard真题：链表按值分割 由leetcode：86分隔列表和148排序链表实现
     * 比如1，4，2，5，2，6，5，7，9，按5分割成3个链表
     * 1，2，4，5
     * 2，5, 6
     * 7，9
     * 然后每个链表排序
     */
    public static List<ListNode> splitListNodeByNumber(ListNode listNode, int target) {
        List<ListNode> list = new ArrayList<>();
        if (Objects.isNull(listNode)) return list;
        ListNode fast = listNode, slow = listNode;
        while (fast != null) {
            if (fast.val == target) {
                fast = fast.next;
                makeNewListNode(list, slow, fast);
                slow = fast;
            } else {
                fast = fast.next;
            }
        }
        if (Objects.nonNull(slow) && Objects.nonNull(slow.next)) makeNewListNode(list, slow, null);
        list.forEach(Test::sortList);
        return list;
    }

    public static void makeNewListNode(List<ListNode> list, ListNode head, ListNode tail) {
        ListNode node = new ListNode(0);
        ListNode t = node, index = head;
        while (index != tail) {
            t.next = index;
            index = index.next;
            t = t.next;
        }
        t.next = null;
        list.add(node.next);
    }

    public static ListNode makeListNode(String str) {
        String[] split = str.split(",");
        ListNode listNode = new ListNode(Integer.parseInt(split[0]));
        ListNode index = listNode;
        for (int i = 1; i < split.length; i++) {
            index.next = new ListNode(Integer.parseInt(split[i]));
            index = index.next;
        }
        return listNode;
    }

    /**
     * 力扣leetcode: 25题：K个一组翻转链表
     * 和上述题的解法很像：
     * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
     * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode node = new ListNode(0);
        node.next = head;
        ListNode slow = node, fast = node.next;
        int index = 1;
        while (fast != null) {
            if (index == k) {
                ListNode leftNode = slow.next;
                ListNode after = fast.next;
                slow.next = null;
                fast.next = null;
                reverseList(leftNode);
                slow.next = fast;
                leftNode.next = fast = after;
                slow = leftNode;
                index -= k;
            } else {
                fast = fast.next;
            }
            index++;
        }
        if (Objects.nonNull(slow.next)) {
            ListNode last = slow.next;
            slow.next = null;
            slow.next = reverseList(last);
        }
        return node.next;
    }


    /**
     * leetcode:148排序链表
     * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
     * 输入：head = [4,2,1,3]
     * 输出：[1,2,3,4]
     * 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
     *
     * @param listNode
     * @return
     */
    public static ListNode sortList(ListNode listNode) {
        return sortList(listNode, null);
    }

    public static ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) return head;
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode fast = head, slow = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sored = merge(list1, list2);
        return sored;
    }

    public static ListNode merge(ListNode list1, ListNode list2) {
        ListNode listNode = new ListNode(0);
        ListNode t = listNode, t1 = list1, t2 = list2;
        while (t1 != null && t2 != null) {
            if (t1.val > t2.val) {
                t.next = t2;
                t2 = t2.next;
            } else {
                t.next = t1;
                t1 = t1.next;
            }
            t = t.next;
        }
        if (t1 != null) {
            t.next = t1;
        } else {
            t.next = t2;
        }
        return listNode.next;
    }

    /**
     * 86.分割链表
     * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
     * 你应当 保留 两个分区中每个节点的初始相对位置。
     */
    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(0);
        ListNode big = new ListNode(0);
        ListNode s = small, b = big;
        while (head != null) {
            if (head.val <= x) {
                s.next = head;
                s = s.next;
            } else {
                b.next = head;
                b = b.next;
            }
            head = head.next;
        }
        s.next = big.next;
        b.next = null;
        return small.next;
    }

    /**
     * 两数之和
     * <p>
     * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
     * 请你将两个数相加，并以相同形式返回一个表示和的链表。
     * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }

    /**
     * 力扣21:
     * 合并两个有序链表，个人认为复习归并排序就好。
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode listNode = new ListNode(0);
        ListNode t = listNode, l1 = list1, l2 = list2;
        while (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                t.next = l2;
                l2 = l2.next;
            } else {
                t.next = l1;
                l1 = l1.next;
            }
            t = t.next;
        }
        if (l1 != null) {
            t.next = l1;
        } else {
            t.next = l2;
        }
        return listNode.next;
    }

    /**
     * 力扣：138.随机链表的复制
     * 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
     * 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。
     * 新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
     * 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
     * <p>
     * 返回复制链表的头节点。
     * <p>
     * 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
     * <p>
     * val：一个表示 Node.val 的整数。
     * random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
     * 你的代码 只 接受原链表的头节点 head 作为传入参数。
     * <p>
     * 思路：回溯+hash表，hash表用来存放指定的原节点和新节点的对应关系
     * 先全局有一个hash表
     */
    public Map<Node, Node> copy = new HashMap<>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        if (!copy.containsKey(head)) {
            Node node = new Node(head.val);
            copy.put(head, node);
            node.next = copyRandomList(head.next);
            node.random = copyRandomList(head.random);
        }
        return copy.get(head);
    }

    /**
     * 206.反转链表
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     * 思路：反向迭代:
     * 先全局定义一个，全局头指针，再定义一个当前指针，指向这个head头指针
     */
    public static ListNode reverseList(ListNode head) {
        ListNode stackNode = null;
        ListNode index = head;
        while (index != null) {
            ListNode next = index.next;
            index.next = stackNode;
            stackNode = index;
            index = next;
        }
        return stackNode;
    }

    /**
     * 反转链表 II：
     * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
     * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode listNode = new ListNode(0);
        listNode.next = head;
        ListNode pre = listNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode after = pre;
        for (int i = 0; i < right - left + 1; i++) {
            after = after.next;
        }
        ListNode leftNode = pre.next;
        ListNode rightNode = after.next;
        pre.next = null;
        after.next = null;
        reverseList(leftNode);
        pre.next = after;
        leftNode.next = rightNode;
        return listNode.next;
    }

    /**
     * 力扣19
     * 删除链表的倒数第 N 个结点
     * 思路：
     * 1.反转两次链表，删除对应的引用。
     * 2.进阶：快慢指针思想 1
     * 0    , 1 , 2   , 3 ,    4 , 5 , null
     * slow , 1 , fast, 3 ,    4 , 5 , null
     * 0    , 1 ,     ,   ,  slow, 5 , fast
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode node = new ListNode(0);
        node.next = head;
        ListNode slow = node, fast = head;
        for(int i = 0; i < n; i++){
            fast = fast.next;
        }
        while(fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
//        ListNode del = slow.next;
//        if(Objects.nonNull(del) && Objects.isNull(del.next)){
//            slow.next = null;
//            return node.next;
//        }
//        slow.next = del.next;
//        del.next = null;
        return node.next;
    }

    /**
     * 力扣：82. 删除排序链表中的重复元素 II
     * 给定一个已排序的链表的头 head，删除原始链表中所有重复数字的节点，只留下不同的数字 。返回已排序的链表 。
     *
     * 思路：一次遍历。有可能删除头节点的链表，就需要用新建的虚拟节点。
     * 具体地，我们从指针cur指向链表的哑节点，随后开始对链表进行遍历。
     * 如果当前 cur.next 与 cur.next.next对应的元素相同，那么我们就需要将 cur.next以及所有后面拥有相同元素值的链表节点全部删除。
     * 我们记下这个元素值 xxx，随后不断将 cur.next从链表中移除，直到 cur.next为空节点或者其元素值不等于 xxx 为止。
     * 此时，我们将链表中所有元素值为 xxx 的节点全部删除。思路是：每次只删一个
     * 如果当前 cur.next 与 cur.next.next对应的元素不相同，
     * 那么说明链表中只有一个元素值为 cur.next的节点，那么我们就可以将 cur指向 cur.next
     * 当遍历完整个链表之后，我们返回链表的的哑节点的下一个节点 dummy.next即可。
     */
    public static ListNode deleteDuplicates(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode node = new ListNode(0, head);
        ListNode i = node;
        while(i.next != null && i.next.next != null){
            if(i.next.val != i.next.next.val){
                i = i.next;
            }else{
                int x = i.next.val;
                while(i.next !=null && i.next.val == x){
                    i.next = i.next.next;
                }
            }
        }
        return node.next;
    }

    /**
     * leetcode.61.旋转链表
     * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
     * 输入：head = [1,2,3,4,5], k = 2
     * 输出：[4,5,1,2,3]
     * 输入：head = [0,1,2], k = 4
     * 输出：[2,0,1]
     * 思路：链表连成环，移动再断开.
     */
    public ListNode rotateRight(ListNode head, int k) {
        ListNode node = head;
        int index = 1;
        while(node.next != null){
            node = node.next;
            index++;
        }
        node.next = head;
        int add = index - k % index;
        while(add-- > 0){
            node = node.next;
        }
        ListNode res = node.next;
        node.next = null;
        return res;
    }
}
